package com.mdnote.practice.dp;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/20
 * @description  乘积最大子数组
 */
public class LeetCode152 {

    public static void main(String[] args) {
        LeetCode152 leetCode152 = new LeetCode152();
        int res = leetCode152.maxProduct(new int[]{-4, -3});
        System.out.println(res);
    }

    public int maxProduct(int[] nums) {
        //  greedy
//        return dp(nums);
        return dpPlus(nums);
    }

    private int dpPlus(int[] nums) {

//        int maxP = Math.max(nums[0], 0), minP = Math.min(nums[0], 0);
        int maxP = nums[0], minP =  nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int max = maxP, min = minP;
            minP = Math.min(nums[i], Math.min(min * nums[i], max * nums[i]));
            maxP = Math.max(nums[i], Math.max(min * nums[i], max * nums[i]));
            res = Math.max(res, Math.max(max, min));
        }
        return res;
    }

    /**
     * 1. 重复子问题： 当前元素num(i) 乘上 前面乘积最大的子数组的值 max(i - 1) 是不是比不乘大
     *                 这里需要注意正负号，我们希望max(i)要么正得很大，要么负得很小，
     * 2. DP数组：dp[i][0]  表示前面i个元素最大乘积
     *           dp[i][1]  表示前面i个元素最小的乘积
     * 3. DP公式：dp[i][0] = Math.max(num[i], dp[i - 1][0] * num[i], dp[i - 1][1] * num[i]
     *           dp[i][1] = Math.min(num[i], dp[i - 1][0] * num[i], dp[i - 1]i] * num[i])
     *  其实你可以分为四种情况思考，1. 当前的数是正数，前面的乘积是正数  --------> 容易获得最大值
     *                         2. 当前的数是正数，前面的乘积为负数  --------> 容易获得最小值
     *                         3. 当前的数为负数，前面的乘积为正数  --------> 容易获得最小值
     *                         4. 当前的数为负数，前面的乘积为负数  --------> 容易获得最大
     *                         四种情况已经在DP公式有所体现了
     * )
     * @param nums
     * @return
     */
    private int dp(int[] nums) {

        // 初始化数组
        int[][] dp = new int[nums.length][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];

        int res = nums[0];
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = Math.max(nums[i], Math.max(dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i]));
            dp[i][1] = Math.min(nums[i], Math.min(dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i]));

            res = Math.max(res, Math.max(dp[i][0], dp[i][1]));
        }
        return res;
    }

}
